import os, sys
sys.path.insert(0, os.path.abspath(os.path.join(os.path.dirname(__file__), '..')))
from sqstack import SqStack

#虽然做对了 但是没有考虑进栈方块置为-1，出栈方块置为0
class Box:
    def __init__(self, x, y, di):
        self.x = x
        self.y = y
        self.di = di

def solve_mg(mg, xi, yi, xo, yo):
    st = SqStack()
    e = Box(xi, yi, -1)
    st.push(e)
    x_index = [-1, 0, 1, 0]
    y_index = [0, 1, 0, -1]
    mg[xi][yi] = -1
    while not st.empty():
        b = st.gettop()
        if b.x == xo and b.y == yo:
            print("find!")
            return st
        di = b.di
        find = False
        while di < 3 and find == False:
            di += 1
            x1 = b.x + x_index[di]
            y1 = b.y + y_index[di]
            if mg[x1][y1] == 0:
                b1 = Box(x1, y1, -1)
                find = True
                mg[b.x][b.y] = -1
            else:
                b.di = -1
                find = False
        if find:
            b.di =di
            st.push(b1)
        else:
            mg[b.x][b.y] = 0
            st.pop()

if __name__ == "__main__":
    xi = yi = 1
    xo = yo = 4
    mg = [[1,1,1,1,1,1],[1,0,1,0,0,1],[1,0,0,1,1,1],[1,0,1,0,0,1],[1,0,0,0,0,1],[1,1,1,1,1,1]]
    st = solve_mg(mg, xi, yi, xo, yo)
    while not st.empty():
        b = st.pop()
        print(b.x, b.y)
    # wow,做对啦


        